/**
 * 
 */
package orgx.wxyz.util;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 匹配括号算法，<br>
 * 该工具类提供了两种匹配方法，<br>
 * 1、静态方法，直接返回所有有括号包含的内容列表，内容中包含括号；<br>
 * 2、实例方法，该方面模拟正则表达式的匹配方式，将对象作为一个匹配器，当有匹配的括号时，输出开始位置和结束位置及内容。<br>
 * 
 * 注意：本工具类有很大的漏洞，主要表现在需求不明确
 * </p>
 * @author zxwang
 * @date 2013-5-20 上午9:04:32
 * 
 */
public class MatchBrackets {

	/**<p>
	 * 
	 * </p>
	 * @param args
	 */
	public static void main(String[] args) {
		String expr = "(A#B)|(A&((B&C)|(B&A))&D&E)|E|F";
//		MatchBrackets match = new MatchBrackets(expr);
//		
//		System.out.println("match: " + match(expr));
//		
//		while (match.find()) {
//			System.out.println("start=" + match.start());
//			System.out.println("end=" + match.end());
//			System.out.println("result=" + match.group());
//		}
		
//		for (String group : find(expr)) {
//			System.out.println(group);
//		}
		
		out(expr);
	}
	
	/**
	 * <p>
	 * 递归输出所有匹配的括号
	 * </p>
	 * @param expr
	 */
	protected static void out(String expr) {
		List<String> groups = find(expr);
		
		if (null == groups || 0 == groups.size()) {
			return ;
		}
		
		for (String group : groups) {
			if (match(group)) {
				out(group.substring(1, group.length() - 1));
			}
			System.out.println(group);
		}
	}
	
	/**
	 * 带括号的表达式字符串
	 */
	private String expr;
	
	/**
	 * 当前查找位置
	 */
	private int index = 0;
	
	/**
	 * 查找完成后，匹配的括号的开始位置
	 */
	private int start = -1;
	
	/**
	 * 查找完成后，匹配的括号的结束位置
	 */
	private int end = -1;
	
	/**
	 * 查找到的匹配括号的字符串
	 */
	private String value = "";
	
	/**
	 * 构造一个括号匹配器
	 * @param expr 大括号的表达式
	 */
	public MatchBrackets(String expr) {
		this.expr = expr;
	}
	
	/**
	 * <p>
	 * 验证括号是否都正确匹配
	 * </p>
	 * @return 正确匹配，则返回true；否则，返回false
	 */
	public static boolean match(String expr) {
		int left = 0;
		boolean bracket = false;
		
		int length = expr.length();
		
		for (int i = 0; i < length; i++) {
			char c = expr.charAt(i);
			switch (c) {
			case '(':
				bracket = true;
				left++;
				break;
				
			case ')':
				left--;
				break;
				
			default:
				break;
			}
		}
		
		// 不为0，则匹配失败
		if (0 != left || !bracket) {
			return false;
		}
		
		return true;
	}
	
	/**
	 * <p>
	 * 查找最外维的多对正确的平行的括号字符串
	 * </p>
	 * @param expr 一条带括号的字符串
	 * @return 匹配的括号内容列表
	 */
	public static List<String> find(String expr) {
		List<String> groups = new ArrayList<String>();
		
		int left = 0;
		int leftIndex = -1;
		int rightIndex = -1;
		
		String group = null;
		int length = expr.length();
		
		for (int i = 0; i < length; i++) {
			char c = expr.charAt(i);
			switch (c) {
			case '(':
				if (-1 == leftIndex) {
					leftIndex = i;
				}
				left++;
				break;
				
			case ')':
				// 若先找到右括号或括号匹配错误，则表达式字符串有错误，直接查找失败，前面查找成功的也将不具有可信任性
				if (leftIndex >= i || left < 0) {
					return new ArrayList<String>();
				}
				
				left--;
				rightIndex = i + 1;
				
				// 查找到一对，直接即可
				if (0 == left) {
					group = expr.substring(leftIndex, rightIndex);
					groups.add(group);
					leftIndex = -1;
				}
				break;
				
			default:
				break;
			}
		}
		
		// 查找到一对，直接即可
		if (0 != left) {
			return new ArrayList<String>();
		}
		
		return groups;
	}
	
	/**
	 * <p>
	 * 查找最外维的一对正确的括号字符串
	 * </p>
	 * @return 查找到，返回true；否则，返回false
	 */
	public boolean find() {
		int left = 0;
		int leftIndex = -1;
		int rightIndex = -1;
		
		String expr = this.expr;
		int length = expr.length();
		
		for (int i = this.index; i < length; i++) {
			char c = expr.charAt(i);
			switch (c) {
			case '(':
				if (-1 == leftIndex) {
					leftIndex = i;
				}
				left++;
				break;
				
			case ')':
				// 若先找到右括号，则表达式字符串有错误，直接查找失败
				if (leftIndex >= i) {
					return false;
				}
				
				rightIndex = i;
				left--;
				
				// 括号匹配错误！
				if (left < 0) {
					this.index = rightIndex + 1;
					return false;
				}
				
				// 查找到一对，直接即可
				if (0 == left) {
					this.start = leftIndex;
					this.end = rightIndex + 1;
					this.value = expr.substring(leftIndex, rightIndex + 1);
					this.index = rightIndex + 1;
					return true;
				}
				break;
				
			default:
				break;
			}
		}
		
		// 不为0或没有匹配到左括号，则匹配失败
		if (0 != left || -1 == leftIndex) {
			return false;
		}
		
		this.start = leftIndex;
		this.end = rightIndex + 1;
		this.value = expr.substring(leftIndex, rightIndex + 1);
		this.index = rightIndex + 1;
		
		return true;
	}
	
	/**
	 * <p>
	 * 返回匹配括号的结果字符串
	 * </p>
	 * @return 结果字符串
	 */
	public String group() {
		return this.value;
	}
	
	/**
	 * <p>
	 * 查找完成后，匹配的括号的开始位置
	 * </p>
	 * @return 开始位置
	 */
	public int start() {
		return this.start;
	}
	
	/**
	 * <p>
	 * 查找完成后，匹配的括号的结束位置
	 * </p>
	 * @return 结束位置
	 */
	public int end() {
		return this.end;
	}
}
